package class_0908red_black_trees;

public class RedBlackTree<K,V> {
    public  enum Color{
        BLACK,
        RED;
    }
    public static class Entry<K extends Comparable<K>, V>{
        K key;
        V value;
        public Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
    }
    public static class Node<K extends Comparable<K>,V>{
        Color color;
        public Entry<K,V> entry;
        Node<K,V> left;
        Node<K,V> right;
        Node<K,V> p;

        public Node(K key, V value){
            this.entry = new Entry<>(key, value);
        }
    }
    private Node root;
    private static Node leafNode = new Node(null,null);
    static{
        leafNode.color = Color.BLACK;
        leafNode.left = leafNode;
        leafNode.right = leafNode;
        leafNode.p = leafNode; ///delete_fixUp操作可能会修改叶子节点的指针， 但无所谓。
    }
    public RedBlackTree(){
        root = leafNode;
    }
    public void inOrderTraversal(){
        inOrder(root);
    }
    public void inOrder(Node head){
        if(head == leafNode){
            return ;
        }
        inOrder(head.left);
        System.out.println("{Key:"+head.entry.key+", value:"+head.entry.value+"}");
        inOrder(head.right);
    }

    /**
     * 脑中把模型图建出来， 代码自然水到渠成。
     * @param T -红黑树
     * @param x -左旋的节点
     */
    private static void LeftRotate(RedBlackTree T,Node x){
        Node y = x.right;
        x.right = y.left;
        if(y.left!=leafNode){
            y.left.p = x;
        }
        y.p = x.p;
        if(x.p == leafNode){
            T.root = y;
        }
        else if(x.p.left==x){
            x.p.left = y;
        }
        else{
            x.p.right = y;
        }
        y.left = x;
        x.p = y;
    }

    /**
     * 右旋的代码实现与左旋对称。
     * @param T
     * @param y
     */
    private static void RightRotate(RedBlackTree T, Node y){
        Node x = y.left;
        y.left = x.right;
        if(x.right!=leafNode){
            x.right.p = x;
        }
        x.p = y.p;
        if(y.p == leafNode){
            T.root = x;
        }
        else if(y.p.right==x){
            y.p.right = x;
        }
        else{
            y.p.left = x;
        }
        x.right = y;
        y.p = x;
    }
    public V search(K key){
        Node cur = root;
        while(cur!=RedBlackTree.leafNode){
            if(cur.entry.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else if(cur.entry.key.equals(key)){
                return (V) cur.entry.value;
            }
            else{
                // cur.key > key
                cur = cur.left;
            }
        }
        return null;
    }
    public void insert(K key, V value){
        Node node = new Node((Comparable) key, value);
        Node p = RedBlackTree.leafNode;
        Node cur = root;
        while(cur!=RedBlackTree.leafNode){
            p = cur;
            if(cur.entry.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else if(cur.entry.key.equals(key)){
                return ;
            }
            else{
                // 逻辑：cur.key > key
                cur = cur.left;
            }
        }
        node.p = p;
        if(p==RedBlackTree.leafNode){
            this.root = node;
        }
        else if(p.entry.key.compareTo(key) < 0){
            p.right = node;
        }
        else{
            p.left = node;
        }
        node.left = RedBlackTree.leafNode;
        node.right = RedBlackTree.leafNode;
        node.color = Color.RED;
        insert_fixUp(this, node);
    }

    /**
     *
     *  // 整个过程只可能违背性质4，性质2， 不过性质二好处理， 全程旋转都围绕着处理相邻红色节点问题。
     * @param T  红黑树
     * @param x  需要进行调整的节点。
     */
    private static void insert_fixUp(RedBlackTree T, Node x){
        //初始状态， x.color = RED;

        //违反了性质4， 红色节点的父亲为黑色。
        while(x.p.color==Color.RED){
            Node uncle; //叔叔节点
            /// 外层的if - else 讨论uncle节点在左或右。
            if(x.p.p.left == x.p){
                uncle = x.p.p.right;
                //case1 : uncle也为红色， 对应变色，在向上调整。
                if(uncle.color == Color.RED){
                    x.p.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    x.p.p.color = Color.RED;
                    x = x.p.p;
                }
                //case2: 拐弯折线双旋
                /// 左旋颠倒父子关系， 弯折线->直折线。
                else{
                    if(x.p.right==x){
                        /// 为什么要先x = x.p, 然后左旋？
                        x = x.p;
                        RedBlackTree.LeftRotate(T, x);
                    }
                    /// its case3. case2->case3, 两者牵连不独立。
                    // x.p,x.p.p颜色对应改变,逮着爷爷节点右旋。
                    x.p.color = Color.BLACK;
                    x.p.p.color = Color.RED;
                    RedBlackTree.RightRotate(T, x.p.p);
                }
            }
            ///以下过程对称处理
            else {
                // x.p.p.right == x.p
                uncle = x.p.p.left;
                if (uncle.color == Color.RED) {
                    x.p.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    x.p.p.color = Color.RED;
                    x = x.p.p;
                } else {
                    if (x.p.left == x) {
                        x = x.p;
                        RedBlackTree.RightRotate(T, x); //弯折线右旋-
                    }
                    x.p.color = Color.BLACK;
                    x.p.p.color = Color.RED;
                    LeftRotate(T, x.p.p);
                }
            }
            ///变色处理一致。
        }
        T.root.color = Color.BLACK;
    }
    private static void transplant(RedBlackTree T, Node u, Node v){
        if(u.p== leafNode){
            T.root = v;
        }
        else if(u.p.left==u){
            u.p.left = v;
        }
        else if(u.p.right==u){
            u.p.right = v;
        }
        v.p = u.p;
    }
    private Node minInum(Node head){
        if(head!=null){
            while(head.left!=leafNode) {
                head = head.left;
            }
        }
        return head;
    }

    /**
     * 基于二叉搜索树删除节点的写法， 稍微添加一些细节， 并补上红黑树的修复部分就大功告成了
     * 值替换太麻烦了， 不通用修改指针链接才是王道。
     * minInum, delete_fixUp, transplant.
     * @param key 删除的节点的关键字。
     */
    public void delete(K key){
        //BST operation
        Node cur = root;
        while(cur!=leafNode){
            if(cur.entry.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else if(cur.entry.key.equals(key)){
                break;
            }
            else{
                cur = cur.left;
            }
        }
        //初始为空树或者删除节点并不存在。
        if(cur==leafNode){
            return ;
        }
        //标记当前节点， 尝试找替换节点
        Node y = cur;
        /// 删除红色节点不会破坏性质5，而且性质4也不会被破坏。
        /// 黑高的部分较难维护，这是一大难点之一。
        Color y_origin_color = y.color;
        Node x;
        if (cur.left==leafNode)
        {
            //左边为空， 右边替换。
            x = cur.right;
            transplant(this, cur, cur.right);
        }
        else if(cur.right==leafNode){
            //右边为空， 左边替换。
            x = cur.left;
            transplant(this, cur, cur.left);
        }
        else{
            // cur.left!=leafNode && cur.right!=leafNode
            y = minInum(cur.right); //找当前节点的后继节点
            y_origin_color = y.color; // 更新一替换的节点颜色
            x = y.right;
            //y.left==leafNode, 不解释，懂一点智慧。
            if(y.p==cur){
                //后继节点是孩子。
                x.p = y.p;
            }
            else{
                //y.p!=cur
                transplant(this, y, x);
                y.right = cur.right;
                y.right.p = y;
            }
            transplant(this, cur, y);
            y.left = cur.left;
            y.left.p = y;
            y.color = cur.color; //染色维持原来的性质。
        }
        //接下来就是调整修复部分了。
        if(y_origin_color == Color.BLACK){
            delete_fixUp(this, x);
        }
    }
    /**
     * 执行删除后，对红黑树的修复工作。
     * @param T
     * @param node
     */
    private static void delete_fixUp(RedBlackTree T, Node x){
        while(x!=T.root&&x.color==Color.BLACK){
            if(x == x.p.left){
                Node uncle = x.p.right;
                if(uncle.color == Color.RED){
                    uncle.color = Color.BLACK;
                    x.p.color = Color.BLACK;
                    LeftRotate(T, x.p);
                    uncle = x.p.right;
                }
                if(     uncle.left.color == Color.BLACK
                    &&
                        uncle.right.color == Color.BLACK)
                {
                    uncle.color = Color.RED;
                    x = x.p;
                }
                else if(uncle.right.color == Color.BLACK){
                    uncle.left.color = Color.BLACK;
                    uncle.color = Color.RED;
                    RightRotate(T, uncle);
                    uncle = x.p.right;
                }
                uncle.color = x.p.color;
                x.p.color = Color.BLACK;
                uncle.right.color = Color.BLACK;
                LeftRotate(T, x.p);
                x = T.root;
            }
            else{
                //(x == x.p.right)
                Node uncle = x.p.left;
                if (uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    x.p.color = Color.BLACK;
                    RightRotate(T, x.p);
                    uncle = x.p.left;
                }
                if (uncle.right.color == Color.BLACK
                        && uncle.left.color == Color.BLACK) {
                    uncle.color = Color.RED;
                    x = x.p;
                }
                else if (uncle.left.color == Color.BLACK) {
                    uncle.right.color = Color.BLACK;
                    uncle.color = Color.RED;
                    LeftRotate(T, uncle);
                    uncle = x.p.left;
                }
                uncle.color = x.p.color;
                x.p.color = Color.BLACK;
                uncle.left.color = Color.BLACK;
                RightRotate(T, x.p);
                x = T.root;
            }
        }
        T.root.color = Color.BLACK;
    }
    //结束了， 再见了红黑树·.
}
